Linear Cover Time is Exponentially Unlikely

LINEAR COVER TIME IS EXPONENTIALLY UNLIKELY

ITAI BENJAMINI, ORI GUREL-GUREVICH, AND BEN MORRIS

Abstract. We show that the probability that a simple random walk
covers a finite, bounded degree graph in linear time is exponentially
small.

More precisely for every D and C, there exists a - a{D, C) > such
that for any graph G, with n vertices and maximal degree D, the proba-
bility that a simple random walk, started anywhere in G, will visit every
vertex of G in its first Cn steps is at most e~ an .

We conjecture that the same holds for a that does not depend on
D, provided that the graph G is simple.

1. Introduction

Let G = [V,E] be a finite connected graph, let {^f}^ be a simple ran-
dom walk on G started at X = v. Let t cov be the cover time of the walk,
i.e. the first time t such that for every veG there is s < t such that X s = v.
Our main result is:

Theorem 1.1. For every D and C, there exists a = a{D, C) > such that
for any graph G, withn vertices and maximal degree D, and every starting
vertex v e V we have

P v {r C0V <Cn)<e- an .

In certain special cases, the result follows from a direct application of
Hoeffding's inequality. For example, if the graph is a path of length n then
the probability to hit the end of the path within Cn steps is exponentially
small. However, this approach fails in general since more typically there
is a fixed probability to have hit any specific vertex by time Cn.

A naive approach to this problem would be to consider the Doob mar-
tingale of some related random variable. Natural choices include either
the cover time itself or the number of uncovered vertices. However, these
martingales could have large differences. For example when considering
a simple random walk on a complete binary tree of height h, if the walk
has already covered half of the tree and is now at the root, the next step

2

ITAI BENJAMINI, ORI GUREL-GUREVICH, AND BEN MORRIS

would cause a very large change in the value of either of these martin-
gales.

The proof of Theorem 11.11 relies heavily on the following fact: The ex-
pected number of visits to a vertex v before covering B v (r) (the ball of
radius r around v) grows to infinity with r, even when we allow the walk
to behave arbitrarily outside of B v {r). To make this more precise, let us
make some definitions.

A stochastic process X t on the vertices of G is said to be a random walk
if X t+ i is a neighbor of X t , almost surely. For a subset of the vertices S^V,
a random walk in S-simple if the distribution of X t+ \ given the history
Xq, ...,X t is uniform on the neighbors of X t whenever X t e S.

For X a random walk on G and S a subset of vertices let t* ov (S) be the
first time t such that X t & S and for every v e S there is 5 < it such that
X s = v. Let £f = \{s< 1 1 X s = v}\ be the number of visits to v until time t.

Lemma 1.2. For every D and C, there exists r = r{D, C), such that ifG is a
graph of maximal degree at most D and v isavertexofG such that B v {r) ^
V, then any B v (r) -simple random walk, started outside B v [r) satisfies

The proof of Theorem l 1 . 1 I then proceeds by constructing a certain sub-
martingale (which is reminiscent of the Doob martingale), which bounds
the cover time from below, has expectation 2Cn and has bounded differ-
ences. Then by Hoeffding's bounds, the value of this submartingale at
time Cn is exponentially unlikely to be less then Cn, which means that
the walk hasn't covered the graph by this time.

Lemma [L2] is of interest in itself. For example, a direct consequence
is the well-known fact that the expected cover time of bounded degree
graphs grows superlinearly in the number of vertices (see subsection ll.ll l.
A more subtle implication is that for this result to hold one only needs the
random walk to be simple in the vicinity of some constant fraction of the
vertices. In particular, the cover time of random walk on a bounded de-
gree graph which is simple in all but a sublinear number of vertice is also
superlinear. In fact, our main Theorem applies to these kind of random
walks as well.

An interesting open question is to determine the right quantitative ver-
sion of 11.21 One can obtain an exponential lower bounded for r in terms
of C (and fixed D) by considering a simple random walk on a d-dimensional

LINEAR COVER TIME IS EXPONENTIALLY UNLIKELY

3

torus, for d > 3. The question is whether the power to change the be-
havior of the walk outside of B v (r) can reduce significantly the expected
number of visits to v before covering.

1.1. Related Works. The cover time of a simple random walk on graphs
is a fairly natural concept which has been studied extensively in the past
30 years. Almost all results about the cover time are about its expecta-
tion. The most important lower bound is that of Feige |3| who proved
that E u (t cov ) > (1 - o{l))n\ogn for any simple graph on n vertices and
any starting vertex u. This implies that the probability to cover the graph
in Cn steps cannot be more than 0(C7 log n) uniformly for all vertices.

The only concentration-type result the authors are aware of is that of
Aldous Q] who proved that if max Mj „ E m (t£. J « max M E m (t cov ) (where t?.
is the first time the walk visits v) then for any starting vertex u we have
Tcov/E m (t C ov) -* 1 in distribution. Notice that our main result applies for
any bounded degree graph, even if the cover time is not concentrated
around its mean.

The interested reader is referred to (2j[4l for further information about
the cover time. More information about the importance of cover times in
Computer Science can be found in (5).

2. Proof of the main Theorem

Given a graph G = ( V, E), a vertex veV and r £ N let A v [r) be the annu-
lus of radius r around v and assume that A v [r) ^ 0. (For the convenience
of the reader, we have included a legend of notation on the last page.)
Given a walk X t on G let & t = a{X Q , ...,X t ) and let £ v (r) = £ v , f „ . .„ be
the number of visits to v before covering and exiting B v {r) (or oo if the
walk never covers B v (r)). Define

L v t (r) = infE(£ v (r)(Y)\& t ) (2.1)

where the infimum is taken over all B v {r) -simple random walks Y that
agree with X in the first t steps (i.e. P(Yb = X , ...,Y t = X t ) = 1). The sto-
chastic process {L v t (r) : t > 0} is adapted to the filtration & t and is some-
what similar to the Doob martingale. However, here we take expectation
with respect to a different process than the random walk itself.

The next few Lemmas show that L v t [r) is, in fact, a submartingale with
bounded differences and that it does not change its value when the walk
is outside oiB v {r).

4

ITAI BENJAMINI, ORI GUREL-GUREVICH, AND BEN MORRIS

Lemma 2.1. L v t {r) is a sub -martingale.
Proof.

E(L v t+l (r) | & t ) = d~ x ) X UL v t+l {r) \ & t ,X t+1 = u)

u~X t

= d ~x] E inf E^ w (r)(n I ^ f ,X f+ i = u)

where for each summand the infimum is taken over all B y (r) -simple ran-
dom walks which agree with X in the first t + 1 steps. Given a vector
{ y"} M ~x f of such random walks we can combine them into a single such
random walk Y in the following way: Y s = X s for 5 < t + 1 and Y s = Y" for
s> t + 1 if Xf+i = a. Obviously, E(L^ +1 (r) | ^ f , X t+ \ = u) is the same under
Y u and under Y . Hence

d~ x ) inf Ue v {r){Y) \ & t ,X t+1 = u) > inf E(f(r)(F) | (2.2)

where the infimum is now taken over all B v {r) - simple random walks which
agree with X in the first t + 1 steps. (In fact we have equality in equation
12.21 . but we don't need this.) In comparison, in the definition of (r)
we have the same expectation but the infimum is taken over all B v {r)-
simple random walks which agree with X in the first t steps. This latter
set contains the former, hence

E(L v t+l (r)\& t )>L v t {r).

m

Lemma2.2. IfX t #B v {r) andX t+l &B v {r) then L v t+l {r) = L v t {r).

Proof. Since the infimum in the definition of V t {r) includes all the B v (r)-
simple random walks Y where Y t +\ = X t +\ with probability 1, we see that
L v t+1 (r) > L v t {r). Similarly, if we have X t+2 = X t then L v t+2 (r) > L v t+l (r).
However, since L v t (r) only depends on X t and on which vertices were vis-
ited in B v {r) and on £ v t and none of these changes between time t and
t + 2 if X t+2 = X t , we get that L v t {r) = L v t+2 {r) > L v t+1 {r) > L v t {r). ■

In fact, when inside B v {r), this process is a martingale and when travers-
ing an edge outside of B v {r) its value doesn't change, so the only times
when L v t (r) exhibits its "sub"-ness is when taking a step from the outside
to the inside of B v {r).

Lemma 2.3. There exists M = M{D, r), such that \V t+l (r) - V t (r) | < M.

LINEAR COVER TIME IS EXPONENTIALLY UNLIKELY

5

Proof. Consider L v t {r) - £ v t . This is the infimum of the expected number
of visits to v between times t and r* 0V {B v {r)) where the infimum is with
respect to any B v {r) -simple random walk that agrees with X in the first
t steps. This number is nonnegative and bounded above by the expecta-
tion when we take the walk X itself. This is at most D 2L>r + 2D r+1 , since
after every visit to v there is a probability of at least D~ 2D ' that X now
performs a depth first search of B v {r), and during such a search the walk
may visit v no more than 2D r+1 times. Since \£ v t+l - £\ I < 1 we get that

\L v t+1 (r) - L v t {r) \ < D 2 ° r+1 + 2D r+1 + 1 .

Now we can turn to the proof of the main result.

Proof of Theorem lLll Given D and C, let r = r(D,4C), as given by Lemma
11.21 If G = (V,E) is a connected graph with maximal degree at most D,
and n = \ V\ > D r+l then for every v e V we have A v {r) ^ 0. Hence, we
can define L v t [r) and we have L„(r) >4Cforall ve V\B Xo {r).
Consider the sum

vEG\B Xo (r)

By Lemma l2TTl we know that L t is a sub -martingale too, since all of the
V t (r) are adapted to the same filtration. Combining Lemmas I2.3l and l2~2l
shows that \L t +\ -L t \< M, provided we incorporate a factor D r+2 into the
constant M = M(D, r) from Lemma l231 We now have

L >4C\V\B Xo {r) \ >3Cn,

for sufficiently large n.

We can now apply the Hoeffding-Azuma inequality to get

P{L t <2Cn)<e- n2l2tM

for any t.

Substituting t = 2Cn we get

P(L 2Cn <2Cn)<e- nl4CM . (2.3)

Let z* ov be the first time t > t cov such that X t & Bx Tcov (2r). Note that
T cov - tcav( B v(r)) for all veV. Note also that if t > T* cm {B v {r)) then £\ >

6

ITAI BENJAMINI, ORI GUREL-GUREVICH, AND BEN MORRIS

£"„ m . ,, = IX for all veV, and summing this inequality over v gives

t = £/?

veV
veV

Thus if L t > t then we must have r* ov {B v (r)) > t for some veV and hence
t* ov > t as well. Thus P(t* ov < t) < P(L f < t). Substituting t = 2Cn gives

P(T* 0V <2Cn) < P(L 2Cn <2Cn)

< -n/4CM

by equation I I2.3I I. Finally we note that P(t* ov - t cov ^ t) decays exponen-
tially fast, at a rate depending only on D and r, regardless of the history
until time t cov . Hence,

P(t cov < Cn) < P(t c * ov < 2Cn) + P(t* ov - t cov > Cn) < e~ an ,

for a constant a that depends only on D and r which in turn depends
only on D and C. ■

3. Proof of the main Lemma

Define

(f){r)=mmE(£ v {r))/d v

where the minimum is take over all connected graphs G = (V, E) of max-
imal degree at most D and vertices v e V such that A v {r) ^ and over
all B V {R) -simple random walks started outside of B v {r). Then one may
restate the main Lemma as

lim (b{r) = oo.

r^oo

We will prove this fact by induction on the value of (p{r). More precisely,
we will show that if (p{r) = K then there is some R> r such that (p{R) >
K+ e~ 3Kd "~ i . Obviously, this is enough, as iterations of K >->■ K + e~ 3Kd "~ 4
tend to infinity.

For a set of vertices Scy write B s {r) = u v£ sB v {r). The following is
a weaker, but more general version of Theorem 11.11 showing that the
weighted sum of the number of visits to a set S of vertices is unlikely to be
small for Bs(r) -simple random walk.

LINEAR COVER TIME IS EXPONENTIALLY UNLIKELY

7

Lemma 3.1. Fix reN and let K = <p{r). For any e > there is some
a = a{r,e) > such that if G - {V,E) is a connected graph of maximal
degree at most D and {a v } ve v a- probability distribution on some S c V
with max v£ sa v < a then for any Bsir) -simple random walk started out-
side B${r) we have

P( X) a v £ v {r) <Kj^ a v d v - e) < e.

veS veS

Proof. For any submartingale L t one can construct a martingale M t such
that

(1) M = L

(2) M t <L t

(3) If L t +i = U then M t+1 =M t

(4) If the differences of L t are bounded by L then the differences of
M t are bounded by 2L

Now, apply this to L v t (r) to get the martingales , and let

M" = lim MY < lim L v Ar) = £ v (r) .

t^oo t— ►oo

It now follows that M v and M M are uncorrelated when the distance be-
tween v and u is more than 2r. This is since M v = M f " +1 (r) - Mj'(r)
and we have (M f y +1 - M^)(M^ +1 - M f M ) = by Lemma E2 and property
3 above and for s ^ t we have E((M," +1 - M v t ){M^ +l - M s ")) = because
these are martingales. Also, the variance of each M v is bounded by the
second moment of £ v {r) which is bounded by some function of D and r
only, since £ v {r) has exponential tails with parameter depending only on
D and R (see Lemma|2]D. Let N = N{D, r) be such a bound for Var(M y ).

Now let

M= £> y M y < J]c/(r).

i/eS yeS

We bound Var(M) by
Var(M) =

X E a v a u Cov(M v ,M u )

veS ueS

X £ «,««Cov(M",M w )

i/eS uinB v {r)

J^a v X aKN/VartAnVartM")

yeS uinB v {r)

E a v aD r+1 N

veS

aD r+1 N.

8

ITAI BENJAMINI, ORI GUREL-GUREVICH, AND BEN MORRIS

and the Lemma holds by choosing a small enough and applying Cheby-
shev's inequality ■

Let T v [r) be the positive hitting time of A v (r) and for w e B v {r) let
a v w {r) = $L w {(j (r ))> where the expectation is with respect to a simple ran-
dom walk. Obviously this expectation is the same for any B v {r) -simple
random walk.

Lemma 3.2. Let G= {V,E) be a finite graph, v e V a vertex and r e N such
that A v {r) ^ 0. Then

£ d w a v w {r) = d v .

weA v {r)

Proof. a v w {r) is equal to the sum of the probabilities of all paths which
start at w and end at v and do not return to A v {r). For each of these
paths, the probability that a simple random walk would traverse it is ex-
actly d v ld w times the probability of traversing it in the reverse direction.
Hence,

£ d w a u w {r) = d v £ P v (X Tv{r) = w) = d v

weA„[r) weA v (r)

where the last equality follows since the walk hits exactly one vertex of
A v (r). M

Let m v [r) = max weAvir) a v w {r).

Lemma 3.3. Given a graph G= (V,E) with maximal degree at mostD and
a vertex v £V and r £ N such thatB v {r) ^ V, there is r' < r such that

Vl ld v a v v {r + \)
m u {r ) < W

for any B v {r) -simple random walk.
Proof. As in Lemma l3~2l we have

d w a v w {r') = d v V v {X Tv[rl) = w)

for every w £ A v {r') when r' < r.

One may bound a v v {f) by considering, for every r' < r all the paths
which start at v, hit A v {r') at some specified vertex w and then hit v again
before returning to A v {r'). For distinct r"s or distinct w in the same A v {r')

LINEAR COVER TIME IS EXPONENTIALLY UNLIKELY

9

these are disjoint sets. This summation yields

alir + 1) > E E VvtX Tv w = w)a v w ir)

r'<r weA„{r')

= E E (a v w {r')fd w /d v

r'<r weA v {r')

> Y.(m v (r')) 2 /d v = r(m v (r)) 2 /d v

r'<r

where the middle equality follows by reversibility. ■
We will also need the following useful Lemma.

Lemma 3.4. Let Xj be a stochastic process on {0, 1}, adapted to the filtration
SFi and let pi = E(x; | . lfpi<\ a.s. for all i, and t is a stopping time
such thatJ^ J i=1 pi < K a.s. then

P(Vi< T ^=0)>e- 3r .

Proof. Define M t = Ylj<i(l ~ Pj)~ l if V ]<i*i = and M t = otherwise. It
is easily checked that Mi is a martingale adapted to S'i and Mo = 1. Since
Pj < \ for all we have l-pj> e~ 3p i so Y\j<i(l ~ Pj)~ l - e 3 ^i- iP K Since
T. r i=1 Pi < K, by the optional stopping Theorem we have P(V ; < T x ; - = 0) >
e~ 3K . m

Now we are ready to prove the main Lemma. Very roughly we show
that for some radius R', by the time we cover A V {R'), we visit v almost
Kd v times in expectation and there is a non-negligible probability that
we haven't visited v at all, in which case we will visit v at least once be-
fore covering, thus increasing the expected number of visits to v before
covering by this probability

Proof of Lemma lL^ Let r be such that K = (p{r). Fix some e to be chosen
later and let a = a{r,e) from LemmaED Let R = D{K + e~ 3Kdl '~ 4 )/ a 2 . We
claim that 0(i?+r) > K+e~ 3Kdu ~ 4 . This is enough to show that linv^oo^r) =
oo.

Let G = ( V, E) be a graph with maximal degree at most D and let v £ V
a vertex such that A V (R) ^ 0. We want to show that for any B V (R) -simple
random walk started outside B V (R) we have E{£ V {R)) > K+e~ 3Kd "~ 4 . If
a v v {R) >K+e~ 3Kdv ~ i then we are done (recall that a v w {R) is the expected
number of visits to v before hitting A V {R) for a simple random walk started
at w) . Hence, from now on we assume that

a v v {R) >K + e~ 3Kd "~ 4 . (3.1)

10 ITAI BENJAMINI, ORI GUREL-GUREVICH, AND BEN MORRIS

In this case, by Lemma 13731 there is R' < R such that for all w e A V {R')
we have

a v w {R')<^ - ~" R - <a.

Let U enumerate the times the walk is in A V {R') and define

bi = e a\ m

7=0 '

and

Ci = e v ..

Claim 3.5. c\ - bi is a martingale (adapted to the filtration &t i+1 )-
Proof. b i+ i - bi = a\ (r) = E(c i+1 - a I ■

In words, we partition the walk into excursions, each of which start and
ends at A v {R'), and for each excursion we count the number of visits to v
and subtract the expectation.

Let I be the first index such that either b\ > Kd v - e or t* 0V CB„ {R+r)) <
tj. Obviously, this is a stopping time and also b\ < Kd v + 1 since a v w {R') <
1, for all w e A V {R').

Claim 3.6.

P(c/ = 0) > e~ 3iKd " +1] .

Proof. The probability to hit v between f ; and tt+i is at most a v x {R') and
^■i=o a x = br< Kd„ + 1. The claim now follows by Lemma l3~4l ■

Claim 3.7.

P(T* ov (v3 y (i? + r)) <tj)<e

Proo/ Obviously, T* 0V (B i; (i? + r)) > T* ov (B s (r)) where S = A V {R'). Let a w =
fl^(-R') < a by our assumption on i?'. Hence, by Lemma l3 . 1 l and the choice
of a we have

P( X) ^^(rX^E a w d w -e)<e

which implies

P(*TS w CB„CR+rn<^-e)<e
and the claim follows by the definition of I. ■

Claim 3.8.

E(d) >{Kd v -£)(!-£).

LINEAR COVER TIME IS EXPONENTIALLY UNLIKELY

11

Proof. E(cj) = E(&j) by Lemma E2 and since / is a stopping time.

E(fcj) > {Kd v - e)P[bi > Kd v - e) > (to^ - e) (1 - e)

by claim 13/71 and the definition of /. ■

Summing it all up, the expected number of visits to v before t* 0V {B v [R+
r)) is at least the expected number of these visits which occur before tj
plus the probability that v has not been visited at all by time tj (in which
case we need to visit it at least once). Lemma [3T81 and Lemma l3^6l bound
these from below yielding

E{£ v {R + r)) > E(c/) + P(c/ = 0)

> [Kd v -e)(l-e) + e- 3{Kdv+1)

> Kd v + e- 3Kd "- 4

for e small enough. ■

Acknowledgements: The authors thank Ariel Yadin for useful discussions.
Legend:

B v {r) - the ball of radius r around v

A v {r) = B v {r) \B v {r- 1) - the annulus of radius r around v

T v {r) the hitting time of A„{r)

£ v t the number of visits to v before time t

£ v (r) the number of visits to v before time r v (r)

Tcov(S) the cover time of S

t cov the cover time of the graph

t* 0V (S) the time to cover and exit S

t* ov the time to cover the graph and exit B Xtcov (2r)

References

[1] D. J. Aldous, Threshold limits for cover times, Journal of Theoretical Probability 4

(1991), 197-211. 10.1007/BF01047002.
[2] D. Aldous and J. Fill, Reversible Markov chains and random walks on graphs, 1999.

Manuscript available at http://www.stat.berkeley.edu/~aldous/RWG/book.html

[3] U. Feige, A tight lower bound on the cover time for random walks

on graphs, Random Struct. Algorithms 6 (1995), no. 4, 433-438, DOI

http://dx.doi.org/ 10. 1002/rsa.3240060406.
[4] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov chains and mixing times, American

Mathematical Society, 2006.
[5] D. Zuckerman, A Technique for Lower Bounding the Cover Time, SLAM J. Disc. Math,

1992, pp. 81-87.

12

ITAI BENJAMINI, ORI GUREL-GUREVICH, AND BEN MORRIS

itai benjamini
Weizmann Institute of Science

E-mail address: itai .benjaminiOweizmann. ac . il

Ori Gurel-Gurevich
University of British Columbia

E-mail address: or igurelOmath . ubc . ca

Ben Morris
University of California, Davis

E-mail address: morrisOmath . ucdavis . edu